#第六章 广度优先搜索
#1.广度优先搜索 是通过节点数多少来计算最短路径的(经过的节点最少为最短路径)
#第七章 狄克斯特拉算法
#1.狄克斯特拉算法 是通过权重计算的最短路径(边长总和的开销最小的为最短路径)

graph = {}
graph['start'] = {}
graph['start']['a'] = 6
graph['start']['b'] = 2

graph['a'] = {}
graph['a']['fin'] = 1

graph['b'] = {}
graph['b']['a'] = 3
graph['b']['fin'] = 5

graph['fin'] = {}

costs = {}
costs['a'] = 6
costs['b'] = 2
costs['fin'] = -1

parents = {}

parents['a'] = 'start'
parents['b'] = 'start'
parents['fin'] = None

processed = [] #处理过的节点

class Node():
    def __init__(self,name,parent):
        self.name = name
        self.parent = parent
    

def find_lowest_cost_node(costs): #找到开销最小的节点
    minVal = -1 
    node = None
    for k,v in costs.items():
        if minVal == -1 and v != -1 and k not in processed:
            minVal = v
            node = k
        elif minVal > v and k not in processed:
            minVal = v
            node = k
    return node

node = find_lowest_cost_node(costs) #找出第一个最小开销的节点进行搜索
parentArr = []
while node is not None:
    cost = costs[node]
    neigbors = graph[node] #该节点的邻居
    print("node=",node)
    for n in neigbors.keys():
        new_cost = cost + neigbors[n] #从节点到邻居的开销
        print("n",n)
        #如果从起点直接前往该节点的开销比经过node再前往该节点的开销大 那么就经过node再前往
        if costs[n] > new_cost or costs[n]==-1: #-1是一个初始值 表示无穷大 需要计算
            costs[n] = new_cost #找到更短的路径前往node的邻居n该节点,所以更新其开销为最少的开销            
            parents[n] = node #更新其父节点
            parentArr.append(Node(n,Node(node,None)))

    processed.append(node) #添加到已检测列表
    node = find_lowest_cost_node(costs)

print(parents) # start->b->a->fin
#print(parentArr)
parentArr.append(Node('start',None))
for n in parentArr:
    print('n.name',n.name)
    if n.parent:
        print("n.parent",n.parent.name)

'''
逻辑总结：
1.如果待搜索列表中还有未搜索的节点n，找出最小消耗的节点
2.找出该节点的邻居并遍历,比较从经过n去到其邻居的开销如果比直接到达该邻居点的开销更小，则更新n的邻居的开销.
3.把n放进已查列表
4.重复1-3步
'''










